/*
MIT License 

Copyright (c) 2021 МГТУ им. Н.Э. Баумана, кафедра ИУ-6, Михаил Фетисов, 

https://bmstu.codes/lsx/simodo
*/

#ifndef simodo_parser_Grammar
#define simodo_parser_Grammar

/*! \file Grammar.h
    \brief Структуры грамматики языка
*/

#include "simodo/ast/Node.h"

#include "simodo/inout/token/Token.h"
#include "simodo/inout/token/LexicalParameters.h"

#include <string>
#include <vector>
#include <map>
#include <set>


namespace simodo::parser
{
    /*!
     * \brief Метод построения таблицы разбора
     */
    enum class TableBuildMethod
    {
        none,   ///< Метод не определён
        SLR,    ///< SLR метод с возможностью решения конфликта S-R
        LR1,    ///< Канонический LR(1) метод построения таблицы разбора
        // LALR,   ///< \todo LALR метод
    };

    /*!
     * \brief Перечисление для определения направления ассоциативности при решении конфликтов по правилам грамматики
     *
     * Большинство правил не вызывают конфликтов, но иногда они возникают.
     * Для реализованного варианта КА разбора синтаксиса (SLR(0) и LR(1)) могут возникать решаемые и нерешаемые конфликты:
     * - Решаемыми могут быть конфликты S-R (сдвиг-свёртка). Для них нужно явно указать приоритет выбора
     *   для конкретного правила. Примером такого конфликта может быть неопределённость вложенного if-if-else в синтаксисе языка C/C++.
     * - Конфликты S-S и R-R для данной реализации разбора не преодолеваются. Для их решения необходимо переписывать
     *   правила грамматики.
     */
    enum class RuleReduceDirection : uint8_t
    {
        Undefined = 0,          ///< Направление свёртки не определено (по умолчанию левоассоциативная)
        LeftAssociative = 1,    ///< Направление свёртки явно задано - левоассоциативная
        RightAssociative = 2,   ///< Направление свёртки явно задано - правоассоциативная
    };

    /*!
     * \brief Правило грамматики с расширенной информацией
     *
     * Грамматика состоит из правил. Каждое правило раскрывает вариант преобразования последовательности входных
     * символов в обобщённый символ, пока входной текст не предстанет самым верхним символом, означающем,
     * что мы доказали принадлежность входной последовательности заданному языку (синтаксису).
     */
    struct GrammarRuleTokens
    {
        inout::Token              production;         ///< Символ продукции
        std::vector<inout::Token> pattern;            ///< Набор символов правой части правила ("шаблон")
        ast::Node                 reduce_action;      ///< Абстрактное синтаксическое дерево действия, выполняемого при свёртке
        RuleReduceDirection       reduce_direction;   ///< Направление свёртки правила в случае неоднозначности (решаемых конфликтов, см. simodo::core::RuleReduceDirection)
    };

    /*!
     * \brief Правило грамматики
     *
     * Грамматика состоит из правил. Каждое правило раскрывает вариант преобразования последовательности входных
     * символов в обобщённый символ, пока входной текст не предстанет самым верхним символом, означающем,
     * что мы доказали принадлежность входной последовательности заданному языку (синтаксису).
     */
    struct GrammarRule
    {
        std::u16string             production;         ///< Символ продукции
        std::vector<inout::Lexeme> pattern;            ///< Набор символов правой части правила ("шаблон")
        ast::Node                  reduce_action;      ///< Абстрактное синтаксическое дерево действия, выполняемого при свёртке
        RuleReduceDirection        reduce_direction;   ///< Направление свёртки правила в случае неоднозначности (решаемых конфликтов, см. simodo::core::RuleReduceDirection)

        /*!
         * \brief Конструктор правила грамматики
         *
         * Конструктор для структуры нужен для удобства её создания.
         *
         * \param prod          Продукция правила (обобщённый символ, в который однозначно можно преобразовать шаблон - pattern)
         * \param patt          Последовательность символов (терминалов и нетерминалов) эквивалентная символу продукции, в который её можно преобразовать
         * \param ast           АСД действия для правила грамматики
         * \param direction     Направление свёртки правила в случае неоднозначности
         */
        GrammarRule(std::u16string prod, std::vector<inout::Lexeme> patt, ast::Node ast,
                    RuleReduceDirection direction=RuleReduceDirection::Undefined)
            : production(prod)
            , pattern(patt)
            , reduce_action(ast)
            , reduce_direction(direction)
        {}
    };

    typedef std::vector<GrammarRule>   GrammarRules_t;  ///< Перечень правил грамматики определяет язык, которому должен
                                                        ///< соответствовать обрабатываемый входной текст

    /*!
     * \brief Структура позиции состояния разбора
     *
     * Перед построением таблицы разбора выполняется формирование перечня состояний. Каждое состояние обслуживает
     * определённый перечень входных символов (терминалов и нетерминалов), которые для него возможны. Каждый такой случай
     * определяется т.н. "позицией". Иначе говоря, позиция состояния разбора определяет точку в шаблоне правила грамматики,
     * обработкой которой данное состояние занимается.
     *
     * Если позиция определена для точки внутри шаблона, то это говорит о необходимости перейти в другое состояние,
     * в котором точка сдвигается на одну позицию вперёд. Если позиция находится за последним символом шаблона, то
     * необходимо выполнить свёртку. Если точка находится перед символом конца файла (EOF), то разбор завершается.
     *
     * Позиции могут быть основные (главные, "main") и неосновные. Основные позиции уникальны и отслеживают продвижение
     * по правилам грамматики. Неосновные позиции необходимы для подстановки в данное состояние всех возможных
     * вариантов раскрытия нетерминального символа на котором стоит основная позиция.
     *
     * Для одного состояния может существовать несколько основных позиций, наличие которых позволяет сократить количество
     * состояний и достичь некоторого компромиса между свободой выбора грамматики языка и сложностью / величиной таблицы.
     * См. https://en.wikipedia.org/wiki/LALR_Fuze.
     *
     * Данная структура необходима только для построения таблицы разбора.
     */
    struct FsmStatePosition
    {
        uint32_t                rule_no;       ///< Номер (индекс) правила в данной грамматике
        uint32_t                position;      ///< Позиция внутри шаблона данного правила, для которой формируется состояние (или которая размещается в состоянии разбора)
        std::set<inout::Lexeme> lookahead;     ///< Постусловие перехода для методов с предпросмотром (например, LR и LALR)
        uint32_t                next_state_no; ///< Номер состояния разбора, в которое нужно переходить в случае сдвига
        bool                    is_main;       ///< Признак основной позиции (основные позиции уникальны и только они могут приводить к свёрткам)

        /*!
         * \brief Конструктор создания позиции
         *
         * Конструктор для структуры нужен для удобства её создания.
         *
         * \param r Номер (индекс) правила грамматики
         * \param p Позиция в шаблоне этого правила
         * \param m Признак основной позиции
         * \param n Номер состояния разбора, в который мы переходим при сдвиге
         */
        FsmStatePosition(uint32_t r, uint32_t p, bool m=true, uint32_t n=0)
            : rule_no(r), position(p), lookahead({}), next_state_no(n), is_main(m)
        {}

        FsmStatePosition(uint32_t r, uint32_t p, std::set<inout::Lexeme> c, bool m=true, uint32_t n=0)
            : rule_no(r), position(p), lookahead(c), next_state_no(n), is_main(m)
        {}
    };

    /*!
     * \brief Перечень состояний КА разбора
     */
    enum class FsmActionType: uint8_t
    {
        Acceptance = 0,     ///< Переход в состояние успешного завершения работы (принимается, что текст соответствует
                            ///< заданному синтаксису); обозначается как Acc
        Shift   = 1,        ///< Приём символа из входного потока и переход в следующее состояние; обозначается как S
        Reduce  = 2,        ///< Выполнение свёртки - внутреннее состояние КА и символ входного потока подходят под одно из правил;
                            ///< обозначается как R
        Error   = 3         ///< Произошла синтаксическая ошибка, нужно выполнить определённое действие для наилучшего восстановления
                            ///< состояния разбора (пока не реализовано)
    };

    typedef std::vector<FsmStatePosition> FsmState_t;   ///< Описание одного состояния грамматики

    typedef uint32_t Fsm_key_t;     ///< Тип упакованного ключа таблицы автомата разбора (символ грамматики + состояние КА)
    typedef uint32_t Fsm_value_t;   ///< Тип упакованного действия (тип действия + значение действия)

    /// \todo Нужно преобразовать в класс.
    /// PVS Studio: V730 Not all members of a class are initialized inside the compiler generated constructor. 
    /// Consider inspecting: first_compound_index, key_bound, value_bound.

    /*!
     * \brief Структура, определяющая грамматику языка
     *
     * Предполагается, что грамматика языка будет загружаться один раз и многократно использоваться для различных входных файлов
     * (см. simodo::apply::GrammarManagement). Иначе говоря, существует два этапа работы с данной структурой:
     * 1. Загрузка структуры грамматики, которая состоит из следующих этапов:
     *    - заполнение правил грамматики (см. simodo::core::GrammarRules_t rules) (важно, что данная процедура может быть выполнена как
     *      с помощью табличного разбора правил (см. simodo::core::PushdownAutomaton), так и с использованием более примитивного парсера
     *      (см. simodo::core::FuzeRdp), предназначенного для начального формирования правил разбора);
     *    - формирование остальных полей структуры грамматики, что производится классом simodo::core::GrammarLoader на основании
     *      правил грамматики, полученных на предыдущем шаге.
     * 2. Использование грамматики, которое выполняется парсером, реализующим табличный метод разбора
     *    (см. simodo::core::PushdownAutomaton).
     *
     * Таблица разбора реализована в виде ассоциативного упорядоченного контейнера (std::map). В качестве ключа выступает
     * упакованные в uint16_t координаты в таблице разбора (номер колонки и номер состояния). Значение
     * представляет собой также упакованную в uint16_t пару: код действия (simodo::core::FsmActionType) и "локатор" действия,
     * смысл которого зависит от действия. Работа с упакованными величинами реализована в части методов данной структуры.
     *
     * В структуре также представлены методы определения индекса колонки таблицы по заданной лексеме.
     */
    struct Grammar
    {
        inout::LexicalParameters        lexical;            ///< Параметры лексики
        inout::uri_set_t                files;              ///< Файлы, по которым строились обработчики
        std::map<std::u16string,ast::Node> handlers;        ///< Именованные СД обработчиков
        GrammarRules_t                  rules;              ///< Правила грамматики
        std::vector<inout::Lexeme>      columns;            ///< Перечень символов грамматики, участвующих в разборе
        size_t                          first_compound_index;///< Начало списка нетерминалов в перечне грамматических символов columns
        TableBuildMethod                build_method = TableBuildMethod::none;
                                                            ///< Метод построения таблицы разбора
        std::vector<FsmState_t>         states;             ///< Состояния автомата разбора
        std::map<Fsm_key_t,Fsm_value_t> parse_table;        ///< Таблица разбора
        Fsm_key_t                       key_bound;          ///< Граница между упакованными в ключе значениями номеров состояний и символов грамматики
        Fsm_value_t                     value_bound;        ///< Граница между упакованными в ячейке значениями номеров действий и значениями переходов/сдвигов/свёрток/типовошибок

        /*!
         * \brief Определение существования в таблице разбора комбинации строки (номера состояния) и колонки (индекса лексемы)
         *
         * В данной реализации таблицы разбора отсутствуют действия над ошибками (хотя они предусмотрены в перечислении
         * simodo::core::FsmActionType). Это позволяет существенно сэкономить память, но требует двойного поиска в контейнере
         * std::map<Fsm_key_t,Fsm_value_t> parse_table сначала поиск, затем вызов метода получения значения simodo::core::Grammar::getFsmValue.
         *
         * \todo Нужно оптимизировать работу с контейнером parse_table, чтобы избежать двойного поиска. А ещё лучше
         * сделать нормальную каноническую таблицу (матрицу) полностью заполненную, и хранить её в матричной структуре
         * типа std::vector<std::vector<T>>. Тогда можно будет избавится от хранения states в Grammar, т.е. не сохранять её в
         * дамп-файл. Это было бы во многом оптимальнее!
         *
         * \param line_no Номер состояния разбора
         * \param col_no  Индекс лексемы (см. std::vector<Lexeme> columns)
         * \return true, если по заданным координатам есть значения и false в противном случае
         */
        bool findFsmValue(size_t line_no, size_t col_no) const
        {
            return parse_table.find(static_cast<Fsm_key_t>(packFsmKey(line_no,col_no))) != parse_table.end();
        }

        /*!
         * \brief Получение значения из таблицы разбора
         *
         * См. комментарий к методу simodo::core::Grammar::findFsmValue.
         *
         * \param line_no Номер состояния разбора
         * \param col_no  Индекс лексемы (см. std::vector<Lexeme> columns)
         * \return Значение из таблицы разбора, в котором упакованы действие и его "локатор"
         */
        Fsm_value_t getFsmValue(size_t line_no, size_t col_no) const
        {
            return parse_table.at(static_cast<Fsm_key_t>(packFsmKey(line_no,col_no)));
        }

        /*!
         * \brief Метод упаковывает номер состояния и индекс лексемы в ключ для контейнера таблицы разбора
         * \param line_no Номер состояния разбора
         * \param col_no  Индекс лексемы
         * \return Упакованное значение ключа для контейнера таблицы разбора
         */
        Fsm_key_t packFsmKey(size_t line_no, size_t col_no) const
        {
            return static_cast<Fsm_key_t>(line_no*key_bound+col_no);
        }

        /*!
         * \brief Метод упаковывает код действия и его "локатор" в значение для контейнера таблицы разбора
         * \param action   Код действия
         * \param location "Локатор" действия
         * \return Упакованное значение для контейнера таблицы разбора
         */
        Fsm_value_t packFsmValue(FsmActionType action, size_t location) const
        {
            return static_cast<Fsm_value_t>(static_cast<size_t>(action)*value_bound+location);
        }

        /*!
         * \brief Метод экстрадирует номер состояния из значения ключа контейнера таблицы разбора
         * \param key Значение ключа
         * \return Номер состояния
         */
        size_t unpackFsmState(Fsm_key_t key) const
        {
            return key / key_bound;
        }

        /*!
         * \brief Метод экстрадирует индекс лексемы в списке доступных из значения ключа контейнера таблицы разбора
         * \param key Значение ключа
         * \return Индекс лексемы в списке допустимых (см. std::vector<Lexeme> columns)
         */
        size_t unpackFsmColumn(Fsm_key_t key) const
        {
            return key % key_bound;
        }

        /*!
         * \brief Метод экстрадирует код действия из значения контейнера таблицы разбора
         * \param val Значение контейнера таблицы разбора
         * \return Код действия (см. simodo::core::FsmActionType)
         */
        FsmActionType unpackFsmAction(Fsm_value_t val) const
        {
            return static_cast<FsmActionType>(val/value_bound);
        }

        /*!
         * \brief Метод экстрадирует "локатор" действия из значения контейнера таблицы разбора
         * \param val Значение контейнера таблицы разбора
         * \return "Локатор" действия
         */
        size_t unpackFsmLocation(Fsm_value_t val) const
        {
            return val%value_bound;
        }

        /*!
         * \brief Метод возвращает индекс лексемы (как терминалов, так и нетерминалов) с полным совпадением
         * \param lexeme Лексема (символ) языка
         * \return Индекс лексемы в контейнере допустимых лексем std::vector<Lexeme> columns или columns.size(), если такой нет
         */
        size_t getColumnIndex(const inout::Lexeme & lexeme) const;

        /*!
         * \brief Метод возвращает индекс терминальной лексемы с учётом обобщения
         * \param lexeme Лексема (символ) языка
         * \return Индекс лексемы в контейнере допустимых лексем std::vector<Lexeme> columns или columns.size(), если такой нет
         */
        size_t getTerminalColumnIndex(const inout::Lexeme & lexeme) const;

        /*!
         * \brief Метод возвращает индекс нетерминальной лексемы
         * \param str Строка нетерминальной лексемы
         * \return Индекс лексемы в контейнере допустимых лексем std::vector<Lexeme> columns или columns.size(), если такой нет
         */
        size_t getCompoundColumnIndex(const std::u16string & str) const;

    };

    /*!
     * \brief Функция возвращает мнемокод действия по заданному значению
     * \param action Значение кода действия
     * \return Мнемоническое обозначение действия
     */
    std::u16string getFsmActionChar(FsmActionType action);

    /*!
     * \brief Получение строкового мнемокода для заданного метода построения грамматических таблиц
     * \param method Метод построения грамматических таблиц
     * \return Строковый мнемокод
     */
    const char * getGrammarBuilderMethodName(TableBuildMethod method);

    /*!
        * \brief Заполнение лексических параметров по сформированной грамматике
        *
        * Структура лексических параметров находится внутри структуры грамматики.
        *
        * \param g Ссылка на грамматику
        * \return true, если успех
        */
    bool fillLexemeParameters(parser::Grammar &g);

    /*!
        * \brief Сохранение параметров грамматики в дамп
        * \param grammar_file Путь к файлу грамматики
        * \param grammar      Ссылка на структуру параметров грамматики
        * \return      Признак успешного сохранения параметров грамматики в заданный файла дампа
        */
    bool    saveGrammarDump(const std::string & grammar_file, const Grammar & grammar);

    /*!
        * \brief Загрузка параметров грамматики из дампа
        * \param grammar_file Путь к файлу грамматики
        * \param grammar      Ссылка на структуру параметров грамматики
        * \return      Признак успешной загрузки параметров грамматики из заданного файла дампа
        */
    bool    loadGrammarDump(const std::string & grammar_file, Grammar & grammar);
}

#endif // simodo_parser_Grammar
